package com.datastructure.test.insertbst;

public class InsertBinaryTree {

    public static void main(String[] args) {

    }

    public TreeNode insertToBST (TreeNode root, int val) {
        // write code here
        TreeNode temp = new TreeNode(val);
        insertBST(root,temp);
        return root;
    }

    private void insertBST(TreeNode root, TreeNode temp) {
        if(root == null){
            return;
        }

        // 判断传入的结点的值和当前子树的根结点的值关系
        if(temp.val < root.val){
            // 如果左结点为空
            if(root.left == null){
                root.left = temp;
            } else { // 如果不为空，递归地向左子树添加
                insertBST(root.left,temp);
            }
        } else { // 添加的结点的值大于当前结点的值
            // 如果右结点为空
            if(root.right == null){
                root.right = temp;
            } else { // 如果不为空，递归增加
                insertBST(root.right,temp);
            }
        }
    }
}

class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
   public TreeNode(int val) {
     this.val = val;
   }
 }
